package problem417;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//417.太平洋大西洋水流问题
//https://leetcode.cn/problems/pacific-atlantic-water-flow/description/

class Solution {
    int[][] st;
    int n,m;
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        n = heights.length;
        m = heights[0].length;
        st = new int[n][m];
        for(int i = 0; i<n; i++) {
            if(st[i][0]!=1) dfs(heights, i, 0, 1);
        }
        for(int j = 0; j<m; j++) {
            if(st[0][j] != 1) dfs(heights,0, j, 1);
        }
        for(int i = 0; i<n; i++) {
            if(st[i][m-1]!=2) dfs(heights, i, m-1, 2);
        }
        for(int j = 0; j<m; j++) {
            if(st[n-1][j] != 2) dfs(heights,n-1, j, 2);
        }
        return ret;
    }
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};
    public void dfs(int[][] heights, int x, int y, int k) {
        if(st[x][y] == 1) {
            ret.add(Arrays.asList(new Integer[] {x, y}));
        }
        st[x][y] = k;
        for(int i = 0; i<4; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];
            if(dx >= 0 && dx < n && dy >= 0 && dy < m 
                && heights[dx][dy] >= heights[x][y] && st[dx][dy] != k) {
                dfs(heights, dx, dy, k);
            }
        }
    }
}